// https://leetcode-cn.com/problems/generate-parentheses/

class Solution {
public:
    vector<string> generateParenthesis(int n)
    {
      if (n == 0)
        return {};

      if (n == 1)
        return { "()" };

      vector<vector<string>> dp(n+1);

      // 1. 0组、1组 括号，能够组成的【所有】情况
      dp[0] = { "" }; // 数组 初始化
      dp[1] = { "()" };

      // 2. 从 2组 括号开始，在前面的基础上，再添加剩下的括号组合
      for (size_t j = 2; j <= n; j++)
      {
        for (size_t i = 0; i < j; i++) // i 遍历 j 左侧（低位组，组成的括号组合数）
        {
          for (string p : dp[i]) // 遍历 i 组括号，组合成的所有括号组合
          {
            for (string q : dp[j - i - 1]) // 遍历【剩下】的（j-i-1 组）括号，组合到 前面已有的括号组合中
            {
              string str = "(" + p + ")" + q;
              dp[j].push_back(str);
            }
          }
        }
      }

      // 3.
      return dp[n];
    }
};